package 校招笔试.华为校招;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/3 20:08
 */
public class P1004 {
    /*
    给定一个大小为n的数组，请问存在多少中方案的子序列使得该子序列的和是原数组元素总和的一半。

       1≤n≤200 数组元素大于0且其总和不超过 10 ^ 5  保证方案总数不超过int的最大值
     */



    /*
      dp , 01 背包
     */


    public static int solution(int nums[]){
        int aim = Arrays.stream(nums).sum() / 2;
        int  len = nums.length;
        int dp[][] = new int[nums.length + 1][aim + 1];
        dp[len][0] = 1;
        for(int i = len - 1;i >= 0;i--){
            dp[i][0] = 1;
            for(int rest = 1;rest <= aim;rest++){
                dp[i][rest] = dp[i + 1][rest];
                if(rest - nums[i] >= 0){
                    dp[i][rest] += dp[i + 1][rest - nums[i]];
                }
            }
        }
        return dp[0][aim];
    }

    public static void main(String[] args) {
        int nums[] = {1,2,3,4,5,6,7};
        System.out.println(solution(nums));

    }



}
